/**
 * @file     minDistance.js
 * @brief    [72. 编辑距离](https://leetcode.cn/problems/edit-distance/)
 * @author   Zhu
 * @date     2023-05-31 06:50
 */

/**
 * Levenshtein 距离，更多实现参考 https://github.com/ka-weihe/fastest-levenshtein
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function (word1, word2) {
    const isArray = Array.isArray;
    const levenshtein = [];

    const len1 = word1.length,
        len2 = word2.length;
    if (len1 && len2) {
        // 初始化
        for (let i = len1; i >= 0; i--) {
            for (let j = len2; j >= 0; j--) {
                if (!isArray(levenshtein[i])) {
                    levenshtein[i] = [];
                }
                if (i && j) {
                    levenshtein[i][j] = 0;
                } else {
                    levenshtein[i][j] = i || j;
                }
            }
        }

        for (let i = 1; i <= len1; i++) {
            for (let j = 1; j <= len2; j++) {
                levenshtein[i][j] = Math.min(
                    levenshtein[i - 1][j] + 1,
                    levenshtein[i][j - 1] + 1,
                    // i，j表示的是长度，所以做下标时要减一
                    levenshtein[i - 1][j - 1] +
                        (word1[i - 1] === word2[j - 1] ? 0 : 1)
                );
            }
        }

        return levenshtein[len1][len2];
    } else {
        return len1 || len2;
    }
};

/**
 * Levenshtein 距离
 * 1. 将二维数组简化到一维
 * 2. 提前剪枝-公共前后缀
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function (word1, word2) {
    if (word1 === word2) return 0;

    let len1 = word1.length,
        len2 = word2.length;

    if (!len1) return len2;
    if (!len2) return len1;

    if (len1 < len2) {
        [word1, word2] = [word2, word1];
        [len1, len2] = [len2, len1];
    }

    // common suffix
    while (word1[len1 - 1] == word2[len2 - 1]) {
        len1--;
        len2--;
    }

    // common prefix
    let start = 0;
    while (start < len2 && word1[start] == word2[start]) {
        start++;
    }

    // previous row
    const prevRow = [];
    // initialize first row
    for (let i = 0; i <= len2; i++) {
        prevRow[i] = i;
    }

    let preCol = 0;
    for (let i = 1; i <= len1; i++) {
        preCol = i;
        let curDiagonal = prevRow[0];
        for (let j = 1; j <= len2; j++) {
            let nextDiagonal = prevRow[j];
            preCol = prevRow[j] = Math.min(
                preCol + 1, // insertion
                prevRow[j] + 1, // deletion
                curDiagonal + (word1[i - 1] === word2[j - 1] ? 0 : 1) // transposition
            );
            curDiagonal = nextDiagonal;
        }
        prevRow[0] = i;
    }

    return preCol;
};
